package com.leetcode.partition4;

import java.io.*;

/**
 * @author `RKC`
 * @date 2022/1/12 14:56
 */
public class LC334递增的三元子序列 {

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] s = reader.readLine().split("\\s+");
        int[] nums = new int[s.length];
        for (int i = 0; i < s.length; i++) nums[i] = Integer.parseInt(s[i]);
        writer.write(increasingTriplet(nums) + "\n");
        writer.flush();
    }

    public static boolean increasingTriplet(int[] nums) {
        //贪心+LIS，最后检查序列里面是否有3个元素
        int[] seq = new int[nums.length];
        int index = 0;
        seq[index++] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            //如果当前元素大于seq的最后一个元素，就直接添加进去；否则使用二分查找到第一个大于等于当前元素的位置，替换为当前元素
            if (nums[i] > seq[index - 1]) seq[index++] = nums[i];
            else {
                //找到第一个大于等于当前数的那个数的位置
                int left = 0, right = index - 1;
                while (left < right) {
                    int mid = (left + right) >>> 1;
                    if (seq[mid] >= nums[i]) right = mid;
                    else left = mid + 1;
                }
                seq[left] = nums[i];
            }
        }
        return index > 2;
    }
}
